
package com.huawei.common.okhttp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.stream.Collectors;

/**
 * 功能描述
 *
 * @author cWX1142527
 * @since 2023年01月18日
 */
public class Java_218_天际线问题 {
    public static void main(String args[]) {
        // int[][] input = new
        // int[][]{{2,9,10},{3,7,15},{5,12,12},{15,20,10},{19,24,8}};
        // int[][] input = new
        // int[][]{{2,9,10},{3,7,15},{5,12,12},{15,20,10},{19,24,10}};
        int[][] input = new int[][]{{0, 2, 3}, {2, 5, 3}};
        List retlist = getSkyline(input);
        System.out.println(retlist);
    }

    public static List<List<Integer>> getSkyline(int[][] buildings) {
        Queue<int[]> queue = new PriorityQueue<>((x, y) -> y[1] - x[1]);
        // 坐标集合
        List<Integer> buildxList = new ArrayList<>();
        List<List<Integer>> retList = new ArrayList<>();
        for (int i = 0; i < buildings.length; i++) {
            buildxList.add(buildings[i][0]);
            buildxList.add(buildings[i][1]);
        }
        buildxList = buildxList.stream().sorted().collect(Collectors.toList());

        for (Integer buildX : buildxList) {
            // 建筑物的左边缘 <= x坐标的 放入优先队列取队首元素就是天极线的坐标点 ， y >= 右边缘取第二高的数据，那么就需要将队列首数据移出,
            // 队列可能会被为空时，那么高度就是0
            // 当堆列为
            int i = 0;
            while (i < buildings.length && buildings[i][0] <= buildX) {
                queue.offer(new int[]{buildings[i][1], buildings[i][2]});
                i++;
            }

            while (!queue.isEmpty() && queue.peek()[0] <= buildX) {
                queue.poll();
            }

            // 首次添加到 天际线坐标集合数据， 最新的天际线 于之前的天际线高度一样时取之前的数据
            int hight = queue.isEmpty() ? 0 : queue.peek()[1];
            if (retList.isEmpty() || retList.get(retList.size() - 1).get(1) != hight) {
                retList.add(Arrays.asList(buildX, hight));
            }
        }
        return retList;
    }
}